//待传输文件被切分成多个部分，按照原排列顺序，每部分文件编号均为一个 正整数（至少含有两个文件）。传输要求为：连续文件编号总和为接收方指定数字 target 
//的所有文件。请返回所有符合该要求的文件传输组合列表。 
//
// 注意，返回时需遵循以下规则： 
//
// 
// 每种组合按照文件编号 升序 排列； 
// 不同组合按照第一个文件编号 升序 排列。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：target = 12
//输出：[[3, 4, 5]]
//解释：在上述示例中，存在一个连续正整数序列的和为 12，为 [3, 4, 5]。
// 
//
// 示例 2： 
//
// 
//输入：target = 18
//输出：[[3,4,5,6],[5,6,7]]
//解释：在上述示例中，存在两个连续正整数序列的和分别为 18，分别为 [3, 4, 5, 6] 和 [5, 6, 7]。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= target <= 10^5 
// 
//
// 
//
// Related Topics 数学 双指针 枚举 👍 584 👎 0


package LeetCode.editor.cn;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ldltd
 * @date 2025-05-18 14:42:54
 * @description LCR 180.文件组合
 */
public class HeWeiSdeLianXuZhengShuXuLieLcof{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 HeWeiSdeLianXuZhengShuXuLieLcof fun=new HeWeiSdeLianXuZhengShuXuLieLcof();
	 	 Solution solution = fun.new Solution();

	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 //在 正整数序列中找出一段连续序列等于target
	//s=na1+(n-1)nd/2  s=na1+(n-1)n/2
	//枚举每个正整数为起点，判断以它为起点的序列和 sum 是否等于 target 即可
    public int[][] fileCombination1(int target) {
			List<int[]> vec = new ArrayList<int[]>();
			int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
			for (int i = 1; i <= limit; ++i) {
				for (int j = i;; ++j) {
					sum += j;
					if (sum > target) {
						sum = 0;
						break;
					} else if (sum == target) {
						int[] res = new int[j - i + 1];
						for (int k = i; k <= j; ++k) {
							res[k - i] = k;
						}
						vec.add(res);
						sum = 0;
						break;
					}
				}
			}
			return vec.toArray(new int[vec.size()][]);
    }
	// 根据求和公式，sum = （a+b)(a-b+1)/2,根据求根公式得到另一部分
	public int[][] fileCombination2(int target) {
		List<int[]> vec = new ArrayList<int[]>();
		int sum = 0, limit = (target - 1) / 2; // (target - 1) / 2 等效于 target / 2 下取整
		for (int x = 1; x <= limit; ++x) {
			long delta = 1 - 4 * (x - (long) x * x - 2 * target);
			if (delta < 0) {
				continue;
			}
			int delta_sqrt = (int) Math.sqrt(delta + 0.5);
			if ((long) delta_sqrt * delta_sqrt == delta && (delta_sqrt - 1) % 2 == 0) {
				int y = (-1 + delta_sqrt) / 2; // 另一个解(-1-delta_sqrt)/2必然小于0，不用考虑
				if (x < y) {
					int[] res = new int[y - x + 1];
					for (int i = x; i <= y; ++i) {
						res[i - x] = i;
					}
					vec.add(res);
				}
			}
		}
		return vec.toArray(new int[vec.size()][]);
	}
	//双指针
	public int[][] fileCombination(int target) {
		List<int[]> vec = new ArrayList<int[]>();
		for (int l = 1, r = 2; l < r;) {
			int sum = (l + r) * (r - l + 1) / 2;
			if (sum == target) {
				//保存结果
				int[] res = new int[r - l + 1];
				for (int i = l; i <= r; ++i) {
					res[i - l] = i;
				}
				vec.add(res);
				l++;
				//如果和小于target，右指针加1
			} else if (sum < target) {
				r++;
				//否则移动左边界
			} else {
				l++;
			}
		}
		return vec.toArray(new int[vec.size()][]);
	}


}
//leetcode submit region end(Prohibit modification and deletion)

}
